674 - Coin change/674.cpp

   1 //647 - Coin change [UVa Online Judge]
   2 //Andrés Mejía-Posada [http://blogaritmo.factorcomun.org]
   3 #include <stdio.h>
   4
   5 #define MAX 7489
   6
   7 unsigned long long dp[2][MAX+1];
   8 //dp[i][j] = numero de maneras en que puedo formar j pesos usando las primeras i monedas
   9 //(Tiene un truco: solo necesitamos la fila anterior así que no es necesario construir toda
  10 //la tabla si no sólo dos filas)
  11 int m[] = {1, 5, 10, 25, 50};
  12 int const coins = 5;
  13
  14 int main(){
  15   dp[0][0] = dp[1][0] = 1LL;
  16   for (int i=0; i<coins; ++i){
  17     for (int a=1; a<=MAX; ++a){
  18       dp[i%2][a] = 0;
  19       if (i > 0){
  20         dp[i%2][a] += dp[(i+1)%2][a];
  21       }
  22       if (a - m[i] >= 0){
  23         dp[i%2][a] += dp[i%2][a - m[i]];
  24       }
  25     }
  26   }
  27
  28   int d;
  29   while (scanf("%d", &d) == 1){
  30     printf("%llu\n", dp[(coins-1)%2][d]);
  31   }
  32   return 0;
  33 }
  34